|
Knapsack Cryptosystems are cryptosystems which security is based on the hardness of solving the knapsack problem. While such systems have been existing for quite a long time, they remain quite unpopular because a lot of such systems have been broken. However that type of cryptosystem is a good candidate for post-quantum cryptography The most famous knapsack cryptosystem is the Merkle-Hellman Public Key Cryptosystem, one of the first public key cryptosystem, published the same year as the RSA cryptosystem. However this system has been broken by several attacks : one from Shamir,〔A. Shamir, ''A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystems,'' Proc. Crypto’82, LNCS, pp.279–288, Springer-Verlag, Berlin, 1982.〕 one by Adleman,〔L. M. Adleman, ''On breaking the titrated Merkle-Hellman public-key cryptosystem,'' Plenum Press. Crypto’82, pp.303–308. 1982.〕 and the ''low density attack''. However there exist modern knapsack cryptosystems that are considered secure so far : among them is Nasako-Murakami 2006.〔T. Nasako and Y. Murakami, ''A high-density knapsack cryptosystem using combined trapdoor,'' the Japan Society for Industrial and Applied Mathematics, Vol.16, No.4, pp.519-605, 2006.〕 What is interesting with those systems is that the Knapsack problem, in the settings where no attack were found, is believed to be difficult to solve even by a quantum computer. This is not the case for systems as RSA relying on the problem of factoring big integers, a problem that is solved in linear time by Shor's quantum algorithm. == References == 〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Knapsack cryptosystems」の詳細全文を読む スポンサード リンク
|